#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
private:

    int findParent(int x, vector<int>& parents) {
        return x == parents[x] ? x : (x = findParent(parents[x], parents));
    }

    void merge(int x, int y, vector<int>& parents) {
        int px = findParent(x, parents);
        int py = findParent(y, parents);
        if (px != py)
            parents[py] = px;
    }


public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> emailToId;
        unordered_map<string, string> emailToName;
        int id = 0;
        for (int i = 0; i < accounts.size(); ++i) {
            for (int j = 1; j < accounts[i].size(); ++j) {
                emailToName[accounts[i][j]] = accounts[i][0];
                if (emailToId.find(accounts[i][j]) == emailToId.end()) {
                    emailToId[accounts[i][j]] = id++;
                }
            }
        }
        vector<int>parents(id);
        for (int i = 0; i < parents.size(); ++i)
            parents[i] = i;
        for (int i = 0; i < accounts.size(); ++i) {
            for (int j = 2; j < accounts[i].size(); ++j) {
                merge(emailToId[accounts[i][1]], emailToId[accounts[i][j]], parents);
            }
        }
        unordered_map<int, vector<string>>map;
        for (auto& it : emailToId) {
            int p = findParent(it.second, parents);
            map[p].push_back(it.first);
        }

        vector<vector<string>>res;
        for (auto& it : map) {
            sort(it.second.begin(), it.second.end());
            res.push_back({ emailToName[it.second[0]] });
            res.back().insert(res.back().end(),it.second.begin(),it.second.end());
        }
        return res;
    }
};